#include <bits/stdc++.h>
#include <vector>
#include <string> 
#include <map>
using namespace std;

//并查集
class UnionFindSet
{

public:
    UnionFindSet(size_t n)
        : _ufs(n, -1), _size(n)
    {
    }
    void Union(int x1, int x2) //合并了两个数据在一个集合
    {
        int root1, root2;
        if ((root1 = FindRoot(x1)) == (root2 = FindRoot(x2))) //本来就在一个并查集，就不需要多此一举
        {
            return;
        }
        if (root1 > root2) //使小的总是做根
        {
            swap(root1, root2);
        }
        _ufs[root2] += _ufs[root1];
        _ufs[root1] = root2;
        _size--;
    }
    int FindRoot(int x) //找到一个数据的根
    {
        int root = x;
        int cnt = 0; //借助cnt来进行压缩，如果有个数找了两次就调整，以达到优化的效果
        while (_ufs[root] >= 0)
        {
            cnt++;
            root = _ufs[root];
        }
        if (cnt > 1)
        {
            _ufs[x] = root;
        }
        return root;
    }
    bool IsSameSet(int x1, int x2) //返回两个值是否在同一个集合
    {
        return FindRoot(x1) == FindRoot(x2);
    }
    size_t SetNums() //返回并查集个数
    {
        return _size;
    }

private:
    vector<int> _ufs;
    int _size;
};

//---------------------------
//如果直接给的是人名等数据，可以用map取绑定数据的关系转换成下标即可

// template <class T>
// class UnionFindSet
// {

// public:
//     UnionFindSet(const T *a, size_t n)
//     {
//         for (size_t i = 0; i < n; i++)
//         {
//             _array.push_back(a[i]);
//             _PeopleDict[a[i]] = i;
//         }
//     }

// private:
//     //这里使用一个map，方便把人编号化。先用数表示之间的关系。最后再通过名字编号也容易
//     std::vector<T> _array;      //人找编号
//     map<T, size_t> _PeopleDict; //编号找人
// };